package Year22_Month05.day25;

import java.util.Arrays;

public class 快速排序1 {
    //hoare版本
    public static void quickSort(int[] arr,int left,int right){
        //首先要明白，如果说当前要排序元素不大于1，那就没有排序的必要
        if(right - left > 1) {
            int index = partion1(arr, left, right);
            quickSort(arr,left,index);
            quickSort(arr,index+1,right);
        }
    }
    public static int partion1(int[] arr,int left,int right){
        //这一步其实是可以省略的，但是为了后面的优化代码这一步我保留
        int index = right - 1;//当前下标是比较元素的下标

        int key = arr[index];
        int begin = left;
        int end = index;
        while(begin < end){
            while (begin < end && arr[begin] <= key){

                begin++;//这一个while循环走完之后确保begin下标对应元素大于key
            }
            while (begin < end && arr[end] >= key){
                end--;//这一个while循环走完之后确保end下标对应元素小于key
            }
            //end > begin的时候就可以进行交换
            if(begin < end){
                swap(arr,begin,end);
            }
        }
        //最后把begin的位置填上key
        swap(arr,begin,right-1);
        return begin;
    }

    public static void swap(int[] array, int left, int right){
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {4,2,8,6,9,1,3,5,0,7};
        quickSort(arr,0,arr.length);
        System.out.println(Arrays.toString(arr));
    }
}
